import java.util.Arrays;

public class Solution {

    public static void main(String[] args) {
        Solution test = new Solution();
        int[] arr = {9,4,2,10,7,8,8,1,9};

        System.out.println(test.maxTurbulenceSize(arr));
    }

    public int maxTurbulenceSize(int[] arr) {
        /**
         * 最长湍流子数组
         *  解题思路：
         *      由题可知，湍流子数组必须满足相邻两数之差不同号 且 不为零
         *      设定 i<j, 此时存在有三种状态：arr[i] < arr[j]; arr[i] == arr[j]; arr[i] > arr[j]
         *      我们将其命名为上升、平行、下降
         *  状态表示：
         *      f[i]表示 以i下标元素为结尾的所有子数组中，状态为上升的最长湍流子数组的长度
         *      g[i]表示 以i下标元素为结尾的所有子数组中，状态为下降的最长湍流子数组的长度
         *  状态转移方程：
         *      if(arr[i] < arr[i-1]) {
         *          g[i] = f[i-1] + 1;
         *          f[i] = 1;
         *      } else if(arr[i] > arr[i-1]) {
         *          f[i] = g[i-1] + 1;
         *          g[i] = 1;
         *      } else {
         *          f[i] = 1;
         *          g[i] = 1;
         *      }
         *  初始化：
         *      由状态转移方程可知，填写i下标的元素需要使用到i-1下标的值
         *      那么在填写0下标位置的元素时就会出现数组越界访问的情况，为了避免，于是手动赋值
         *      f[0] = g[0] = 1;
         *      再次观察到，所有位置的最差情况均为-1，因此我们将dp表整体初始化为1
         *  填表顺序：
         *      从左到右
         *  返回值：
         *      返回两表中最大值
         * */
        // 1 预处理
        int n = arr.length;
        // 2 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        // 3 初始化
        Arrays.fill(f, 1);
        Arrays.fill(g, 1);
        // 4 填表
        int maxLength = 1;
        for(int i = 1; i < n; i++) {
            if(arr[i] < arr[i-1]) {
                g[i] = f[i-1] + 1;
                maxLength = Math.max(g[i], maxLength);
            } else if(arr[i] > arr[i-1]) {
                f[i] = g[i-1] + 1;
                maxLength = Math.max(f[i], maxLength);
            }
        }
        // 5 返回值
        return maxLength;
    }
}
